//插入排序
//就像打扑克牌一样，不断地将后面的牌按照从小到大的顺序向前移动进行排序
//为数字数字寻找合适的位置坐下

//时间复杂度O(n2)，空间复杂度O(1)

//排序算法的稳定性：
//假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，
//即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
//https://leetcode-cn.com/leetbook/read/sort-algorithms/ev1l5g/
//一般而言，冒泡排序和插入排序都是稳定的，而选择排序是不稳定的。
//但排序算法的稳定性是相对的，与具体实现方式有关系，不能一概而论。

public class insertSort {
    public static void main(String[] args) {
        int[] nums = new int[]{6,2,3,1,5,4};
        insertSort(nums);
        for(int i = 0 ; i < 6 ; i++){
            System.out.println(nums[i]);
        }
    }

    public static int[] insertSort(int[] nums){
        //i不断向后移，j不断向前移，实现较小的数向前移动排序
        for(int i =1 ; i < nums.length ; i++){
            for(int j = i-1 ; j >=0 ; j--){
                if(nums[j] > nums[j+1]){
                    int tmp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = tmp;
                }
            }
        }
        return nums;
    }
}
